// TopK.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

#include "TFun.h"

void TopKAlgorithm(const vector<int> &inputArray, int nTopK)
{
	TFun obj("TopKAlgorithm");

	vector<int> vec(inputArray.begin(), inputArray.begin()+nTopK);
	make_heap(vec.begin(), vec.end(), greater<int>());

	for (int i = nTopK; i < inputArray.size(); i++)
	{
		if (inputArray[i] > vec[0])
		{
			vec[0] = inputArray[i];
			make_heap(vec.begin(), vec.end(), greater<int>());
			//pop_heap(first, nTopK, i, inputArray[i], distance_type(first));
		}		
	}

	sort(vec.begin(), vec.end(), greater<int>());
	copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, ", "));
}

void Partial_sort(int inputArray[], int nInputLen, int nTopK)
{
	vector<int> vec(inputArray, inputArray+nInputLen);

	TFun obj("Partial_sort");

	partial_sort(vec.begin(), vec.begin()+nTopK, vec.end(), greater<int>());

	sort(vec.begin(), vec.begin()+nTopK, greater<int>());
	copy(vec.begin(), vec.begin()+nTopK, ostream_iterator<int>(cout, ", "));
}

void TopKNth(int inputArray[], int nInputLen, int nTopK)
{
	vector<int> vec(inputArray, inputArray+nInputLen);

	TFun obj("TopKNth");

	nth_element(vec.begin(), vec.begin()+nInputLen-nTopK, vec.end());		

	sort(vec.end()-nTopK, vec.end(), greater<int>());
	copy(vec.end()-nTopK, vec.end(), ostream_iterator<int>(cout, ", "));
}


int _tmain(int argc, _TCHAR* argv[])
{
	vector<int> data;

	int val = 0;
	while (cin >> val)
	{
		//cout << val << endl;
		data.push_back(val);
	}

	TopKAlgorithm(data, 10);

	TopKNth(&data[0], data.size(), 10);

	Partial_sort(&data[0], data.size(), 10);

	return 0;
}

